import java.util.*;
public class Test {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    /*
    题目 1 ：两颗相同的二叉树
     */
    //给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        if(q == null && p == null){
            return true;
        }
        //走到这，两棵树都非空，那么就看值相不相等了
        if(q.val != p.val){
            return false;
        }
        boolean retLeft = isSameTree(p.left,q.left);
        boolean retRight = isSameTree(p.right,q.right);
        return retLeft && retRight;
    }

    /*
    题目 2 : 二叉树是否对称，与两颗二叉树是否相同这个题目类似！
     */
    public boolean isSymmetric(TreeNode root){
        boolean ret = isChildSymmetric(root.left,root.right);
        return ret;
    }
    private boolean isChildSymmetric(TreeNode leftRoot,TreeNode rightRoot){
        if(leftRoot == null && rightRoot == null){
            return true;
        }
        if(leftRoot == null && rightRoot != null || leftRoot != null && rightRoot == null){
            return false;
        }
        if(leftRoot.val != rightRoot.val){
            return false;
        }
        boolean ret1 = isChildSymmetric(leftRoot.left,rightRoot.right);
        boolean ret2 = isChildSymmetric(leftRoot.right,rightRoot.left);
        return ret1 && ret2;
    }

    /*
    题目 3 ： 翻转 二叉树
     */
    //从上往下依次交换
    public TreeNode invertTree1(TreeNode root) {
        if(root == null){
            return null;
        }
        if(root.left == null && root.right == null){
            return root;
        }
        swap(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    private void swap(TreeNode root){
        TreeNode cur = root.left;
        root.left = root.right;
        root.right = cur;
    }
    //存在的问题是，多次出现的返回值没有利用起来
    //从叶子节点开始交换
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    /*
    题目 4 ： 二叉树的最大深度
     */
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;

    }

    /*题目 5 ：二叉树的层序遍历
     */
    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> temp = new LinkedList<>();
            while(size > 0){
                TreeNode cur = queue.poll();
                temp.add(cur.val);
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            list.add(temp);
        }
        return list;
    }

    /*
    题目 6 ： 路径总和
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return targetSum == root.val;
        }
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum( root.right,targetSum - root.val);
    }

    /*
    题目 7 ： 二叉搜索树中的搜索
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        return searchBST(root.val > val ? root.left : root.right,val);
    }
    /*
    题目 8 ： 二叉搜索树中的插入
     */
    //自己写的版本，有点繁琐！
    public TreeNode insertIntoBST1(TreeNode root, int val) {
        if(root == null){
            root = new TreeNode(val);
            return root;
        }
        TreeNode cur = root;
        while(((cur.val > val) ? cur.left : cur.right) != null){
            cur = cur.val > val ? cur.left : cur.right;
        }
        if(cur.val > val){
            cur.left = new TreeNode(val);
        }else{
            cur.right = new TreeNode(val);
        }
        return root;
    }
    //官方版本，思路一样，但代码可读性比自己写的强！
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while(pos != null){
            if(pos.val > val){
                //pos 的左边为空，pos 的位置不动，直接赋值
                if(pos.left == null){
                    pos.left = new TreeNode(val);
                    break;
                }else{
                    //pos 的左边不为空，那么继续迭代！
                    pos = pos.left;
                }
            }else{
                if(pos.right == null){
                    pos.right = new TreeNode(val);
                    break;
                }else{
                    pos = pos.right;
                }
            }
        }
        return root;
    }

    /*
    题目 9 ： 判断是否为二叉搜索树！
     */
    //最原始的想法：根节点的左边所有节点，都比根节点的值小，而右边的所有节点都应该比根节点大
    //然后根节点的左孩子，其左节点都应该小，而右边比它大！
    //依次类推，每颗子树都这么判断
    //缺点：整个二叉树遍历好多遍！！时间复杂度太高！！
    //二叉搜索树的中序遍历是升序的！！
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return false;
        }
        double num = -Double.MAX_VALUE;
        //利用非递归的中序遍历！！
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if(cur.val <= num){
                return false;
            }
            num = cur.val;
            cur = cur.right;
        }
        return true;
    }
    public static void main(String[] args) {
        int num = -Integer.MAX_VALUE;
        System.out.println(num);
    }
}
